P4588 数学计算

题目描述

小豆现在有一个数 $x$，初始值为 $1$。小豆有 $Q$ 次操作，操作有两种类型：

1 m：将 $x$ 变为 $x\times m$，并输出 $xmodM$

2 pos：将 $x$ 变为 $x$ 除以第 $pos$ 次操作所乘的数（保证第 $pos$ 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 $xmodM$。

输入格式

第一行是两个数字 $Q,M$。

接下来 $Q$ 行，每一行为操作类型 $op$，操作编号或所乘的数字 $m$（保证所有的输入都是合法的）。

$1\le Q\le {10}^5$，$t\le 5,M\le {10}^9$，$0<m\le {10}^9$。

输出格式

对于每一个操作，输出一行，包含操作执行后的 $xmodM$ 的值。

Solution

线段树

乍一看是数论，可是如果是用逆元的话，mod 不一定为质数，做不了。

用的是线段树区间乘法，当要除的时候，由于题目说了 对于每一个类型 1 的操作至多会被除一次 所以，只需要将之前操作要乘的数修改为 1 即可。就不会有精度问题。

#define lc u<<1
#define rc u<<1|1
int mod;
struct Tree { //线段树
    ll l, r, sum;
}tr[400010];

void pushup(ll u) { //上传
    tr[u].sum = (tr[lc].sum * tr[rc].sum) % mod;
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,0};
    if (l == r) {
        tr[u].sum = 1;
        return;
    } 
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
void change(ll u, ll l, ll r, ll k) { //区修
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum = k;tr[u].sum %= mod;
        return;
    }
    ll m = tr[u].l + tr[u].r >> 1;
    if (l <= m) change(lc, l, r, k);
    if (r > m) change(rc, l, r, k);
    pushup(u);
}
void solve() {
    int n;cin >> n >> mod;
    build(1, 1, n);
    for (int i = 1;i <= n;i++) {
        int op, x;cin >> op >> x;
        if (op == 1) {
            change(1, i, i, x);cout << tr[1].sum << '\n';//将后面需要乘的数字加入并更新
        } else {
            change(1, x, x, 1);cout << tr[1].sum << '\n';//将x位置要乘的数修改为1并更新
        }
    }
}